package rank;

public abstract class AbstractRank {
	public RankNode first;
	public RankNode last;
	
	private int _count = 0;
	
	protected abstract RankNode initFirstNode();
	protected abstract RankNode initLastNode();

	public AbstractRank() {
		first = initFirstNode();
		first.setRanking(0);
		last = initLastNode();
		last.setRanking(Integer.MAX_VALUE);
		last.font = first;
		first.back = last;
	}

	public int count() {
		return _count;
	}

	synchronized public void pushBack(RankNode node) {
		node.setRanking(_count+1);
		
		insertBefore(node, last);
		
		update(node);
		
		_count++;
	}
	
	//[)
	public void updateRanking(RankNode from, RankNode to) {
		RankNode ite = from;
		while (ite != to) {
			if (ite == last) return;
			ite.setRanking(ite.font.getRanking()+1);
			ite = ite.back;
		}
	}

	synchronized public RankNode remove(RankNode node) {
		link(node.font, node.back);
		_count--;
		updateRanking(node.back, last);
		return node;
	}

	private void insertBefore(RankNode a, RankNode b) {
		link(b.font, a);
		link(a, b);
	}

	private void insertAfter(RankNode a, RankNode b) {
		link(a, b.back);
		link(b, a);
	}

	private void link(RankNode a, RankNode b) {
		a.back = b;
		b.font = a;
	}

	synchronized public void update(RankNode node) {		
		link(node.font, node.back);
		
		int ranking;
		
		RankNode ite = node.font;
		
		if (node.compareTo(ite) > 0) {
			while (node.compareTo(ite) > 0) {
				ranking = ite.getRanking();
				node.setRanking(ranking);
				ite.setRanking(ranking+1);
				ite = ite.font;
			}
			insertAfter(node, ite);
			return;
		}
		
		ite = node.back;
		if (node.compareTo(ite) < 0) {
			while (node.compareTo(ite) < 0) {
				ranking = ite.getRanking();
				node.setRanking(ranking);
				ite.setRanking(ranking-1);
				ite = ite.back;
			}
		}
		
		insertBefore(node, ite);
	}
	
	public RankNode pop() {
		if (last.font == first) return null;
		return remove(last.font);
	}
}
